package com.leetcode.algs4.graph;

import java.util.Stack;

/**
 * @author Dennis Li
 * @date 2020/6/16 13:29
 */
public class DepthFirstPaths {
    private boolean[] marked;
    // 比如需要从3开始遍历到4,5；5找到后返回到，再从3到4
    // 那么edgeTo[5] = 3; edgeTo[4] = 3; -- 都是从3到这两个点
    private int[] edgeTo; // 从起点到一个顶点的已知路径上的最后一个顶点
    private final int s;

    public DepthFirstPaths(Graph G, int s) {
        marked = new boolean[G.V()];
        edgeTo = new int[G.V()];
        this.s = s;
        dfs(G, s);
    }

    private void dfs(Graph G, int v) {
        // 访问到该顶点，置为true
        marked[v] = true;
        for (int w : G.adj(v)) {
            // 如果没有访问过
            if (!marked[w]) {
                // 将路径添加到数组中
                edgeTo[w] = v;
                dfs(G, v);
            }
        }
    }

    public boolean hasPathTo(int v) {
        return marked[v];
    }

    public Iterable<Integer> pathTo(int v) {
        if(!hasPathTo(v)) return null;
        Stack<Integer> path = new Stack<>();
        // 根据路径点，依次入栈，最后将起点入栈，后进先出弹出。得到路径
        for (int i = v; i != s ; i = edgeTo[i]) {
            path.push(i);
        }
        path.push(s);
        return path;
    }

}
